/*
 * @lc app=leetcode.cn id=238 lang=cpp
 *
 * [238] 除自身以外数组的乘积
 */

// @lc code=start
class Solution
{
public:
  vector<int> productExceptSelf(vector<int>& nums)
  {
    int n = nums.size();
    vector<int> prefix(n), suffix(n), ans(n);
    prefix[0] = nums[0];
    suffix[n - 1] = nums[n - 1];
    for (int i = 1; i < n; ++i)
      prefix[i] = prefix[i-1] * nums[i];
    for (int j = n - 2; j >= 0; --j)
      suffix[j] = suffix[j + 1] * nums[j];
    for (int k = 0; k < n; ++k) {
      int prev = k - 1 >= 0 ? prefix[k - 1] : 1;
      int next = k + 1 < n ? suffix[k + 1] : 1;
      ans[k] = prev * next;
    }
    return ans;
  }
};
// @lc code=end
